package gold.digger;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC416 {


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 0-1背包倒序更新dp数组，太精妙了！
     * @return:
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 != 0) {
            return false;
        }

        sum /= 2;
        boolean dp[] = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }

        return dp[sum];
    }


    public boolean canPartitionT(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        if (sum % 2 != 0) {
            return false;
        }

        sum /= 2;
        Arrays.sort(arr);
        int curSum = 0;
        for (int i = 0; i < arr.length / 2; i++) {
            curSum += arr[i];
        }

        for (int i = arr.length / 2; i < arr.length && curSum < sum; i++) {
            curSum += arr[i];
        }

        if (curSum != sum) {
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        LC416 an = new LC416();

        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.out.println(an.canPartitionT(arr));
    }
}
